package com.dy.分类.数组._60_第k个排列;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public String getPermutation(int n, int k) {
        StringBuilder sb = new StringBuilder();
        List<Integer> list = new ArrayList<>(n+1);
        //list中顺序存入未使用的数字
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        //计算 n-1!
        int tmp = 1;
        for (int i = 1; i < n; i++) {
            tmp = tmp * i;
        }
        //当n大于1 的时候
        while(n>1) {
            //去找第一个数字
            int j = k / tmp;
            //余数,是剩下的需要的排列
            k = k % tmp;
            n--;
            tmp = tmp/n;
            if(k==0){
                sb.append(list.get(j-1));
                list.remove(j-1);
                break;
            }else{
                sb.append(list.get(j));
                list.remove(j);

            }
        }
       for(int i=list.size()-1;i>=0;i--){
           sb.append(list.get(i));
        }
       return sb.toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.getPermutation(3,4);
    }
}
